package com.demo300_最长递增子序列;

import java.util.ArrayList;
import java.util.TreeSet;

/**
 * 把 491题中的求递增子序列问题, 稍微转变一下.   把每次对结果的收集转变为对这个 集合中元素个数的一个大小比较,
 *
 * 并且求其最大值
 *
 * 测试通过 36/54 , 相比于之前的22 ,有进步但是不是太明显~  还需要再进行一个操作~
 */
public class Solution_剪枝 {
    public static int max;
    public static void main(String[] args) {

    }
    public int lengthOfLIS(int[] nums) {
        ArrayList<Integer> path = new ArrayList<>();
        dfs(nums,path,0);

        return max;
    }

    private void dfs(int[] nums, ArrayList<Integer> path, int startIndex) {
        // 求max的最大值
        max=max==0?path.size():Math.max(max,path.size());
        // 边界条件:
        // 这次不写边界条件了

        // 遍历 + 递归的逻辑
        TreeSet<Integer> set = new TreeSet<>();
        for (int i = startIndex; i < nums.length; i++) {

            // 去重
            if (!set.add(nums[i])){
                continue;
            }
            // 对当前元素进行一个判断
            if (path.size()>0&&nums[i]<=path.get(path.size()-1)){
                continue;
            }

            // 剪枝操作
            // 如果这个集合中的元素 + 这个 剩余的元素 < max , 那么可以直接退出这次的循环了
            if (path.size()+(nums.length-1-i+1) < max){
                return;
            }

            path.add(nums[i]);

            // 递归
            dfs(nums,path,i+1);

            // 回溯
            path.remove(path.size()-1);
        }
    }
}
